1. Field of the Invention
The present invention relates to scheduling circuitry and methods for use, for example, in scheduling cell transmission operations in an asynchronous transfer mode (ATM) communications network.
2. Description of the Related Art
In an ATM communications network a plurality of so-called xe2x80x9cvirtual channelsxe2x80x9d (VCs) are used to transmit user data and control information between different network units. Such user data and control information is transmitted in the form of ATM cells, each cell having a header portion, containing control and addressing information for the cell, and a payload portion containing the user data or other control information.
A given network unit may have a plurality of such virtual channels connecting it to one or more other units of the network. It is therefore necessary to provide, in each network unit, a traffic manager that manages the times at which cells are caused to be applied to the different virtual channels concerned.
The task of the traffic manager is complicated by the fact that different virtual channels may be used to transmit different types of traffic, including traffic types having different so-called priorities. For example, the following types of traffic may occur in ATM networks:
i) Constant bit rate (CBR) traffic. This is typically used for high-priority data which should not be subject to delays, for example video signals.
ii) Variable bit rate (VBR) traffic. This type of traffic also has a relatively high priority (but lower than CBR traffic). It is used where some tolerance to delay is available, for example compressed video (e.g. Motion Picture Expert Group MPEG2) traffic or voice traffic.
iii) Available bit rate (ABR) traffic. A virtual channel used to transmit ABR traffic has traffic parameters that are agreed between the user of the channel and the network operator. Within the limitations imposed by the agreed parameters, the ABR channel is permitted to vary its transmission rate so as to take advantage of spare capacity in the network. ABR traffic has a low priority (lower than CBR and VBR traffic). ABR channels may be used, for example, for file and data transfers.
iv) Unspecified bit rate (UBR) traffic, for example e-mail and some types of data/file transfers.
FIG. 1 of the accompanying drawings is a schematic block diagram for use in explaining a xe2x80x9ccalendarxe2x80x9d scheduling method proposed previously for managing the cell transmission times from an ATM network unit.
In FIG. 1, a calendar 1 is made up of a list of storage locations 2 corresponding respectively to a succession of time slots. The duration of each time slot is equal to the time taken to transmit a single ATM cell at the maximum required data rate of the ATM network.
Each storage location 2 is capable of storing one or more entries, each such entry denoting that a specified virtual channel is to be serviced by the traffic manager in the time slot to which the storage location corresponds. For example, a storage location 2A in the calendar 1 has a single entry denoting that the virtual channel VCw is to be serviced by the traffic manager in the time slot corresponding to the storage location 2A.
It is possible for more than one VC to be entered into the same storage location. For example, a storage location 2B in the calendar 1 has three virtual channels VCx, VCy and VCz entered therein, denoting that each of these channels is to be serviced in the time slot corresponding to the storage location 2B. The three entries in the storage location 2B are made in the form of a linked list, so as to avoid reserving large amounts of memory per time slot to attempt to accommodate the largest possible number of VCs which could accumulate at a particular storage location.
The traffic manager uses two pointers 3 and 4 to process the calendar 1. The first of these pointers 3 is a current time pointer (T) which represents real time. The current time pointer T is always incremented after each cell interval. The second pointer 4 is an activity pointer (A) which is always attempting to catch up with the T pointer 3, without ever being incremented past it.
At each storage location 2 in the calendar 1, if no VCs are entered, the A pointer is simply incremented to the next storage location, so that in this case the A pointer will tend to catch up to the T pointer. If, on the other hand, one or more VCs is entered at a storage location pointed to by the A pointer, the pointer is not incremented until all the VCs have been processed (in this case the T pointer will be incremented more than once during the time required to process all the VCs concerned, so that the A pointer will tend to fall further behind the T pointer).
The traffic manager services the entries in the calendar as follows. Firstly, a cell for the VC specified in the entry is transmitted. Secondly, if necessary, a new inter-cell interval for the channel is calculated (CBR channels always have the same inter-cell interval but for VBR, ABR and UBR channels the cell interval can vary in use of the channel and so must be recalculated from time to time). The next cell transmission for the specified VC is then rescheduled by making a new entry for the VC in a different storage location 2 of the calendar 1.
For example, if VCx has 33% of the available transmission capacity from the ATM network unit concerned, when it is serviced at location 2B it will be rescheduled at storage location 2C, three cell time slots ahead of the current time pointer T.
Incidentally, in this example, it can be seen that the A pointer, which at this time is pointing to the storage location 2B, is five storage locations behind the T pointer. Some catching up of the A pointer to the T pointer will be possible because of the empty storage locations between the two pointers but there are also three virtual channels VCy, VCz and VCw to service between the A and T pointers. This means that in practice it will be more than three cell periods before VCx will be encountered again for further processing.
One problem with the calendar scheduling method shown in FIG. 1 is that it is necessary to be able to cope with channels having very different transmission rates. Each cell period in an ATM network having a maximum data rate of 155 Mbps is 2.726 xcexcs. However, some types of VC can have very low cell rates. For example, ABR channels use resource management (RM) cells for control purposes and the cell rates for such RM cells may be only 10 cells per second. This would require the calendar 1 in FIG. 1 to have 35000 entries (i.e. 35000xc3x972.726 xcexcs=0.1 s). This is impractical, as the calendar 1 requires a storage location 2 for each time slot.
One solution to this problem, proposed previously, is to include a counter with each VC, which counter is set initially to a certain positive value and then decremented on each pass around the calendar as each VC entry is examined by the traffic manager. The VC is only serviced (i.e. a cell transmitted and the next cell transmission scheduled) when its counter reaches 0. In this way, it is possible to reduce the size of the calendar to (say) 1000 storage locations, using a six-bit counter per VC. VCs whose cell rates are greater than 370 cells per second (an inter-cell period of 2.7 milliseconds at 155 Mbps) are always xe2x80x9chitxe2x80x9d in the calendar, i.e. the counter for each such VC is permanently 0.
Although the solution outlined above is partially effective in reducing the calendar size, it is wasteful of traffic manager resources in that, even though a particular VC is encountered on each pass through the calendar, this does not necessarily mean that it should be serviced on each encounter. Often, therefore, entries are read by the traffic manager which do not require any servicing on this particular pass of the calendar.
A further disadvantage is associated with the need for each entry in the calendar to have a backward pointer (to the previous entry in the linked list) as well as a forward pointer. Because each VC has its own counter, and a linked list is processed from beginning to end, only those VCs whose respective counters are zero are no longer required. The remaining VCs in the linked list, whose respective counters are non-zero, must be retained in the linked list for the next calendar pass. To enable a VC whose counter has become zero to be removed from the linked list whilst still retaining the other (non-zero-counter) VCs, it is necessary to use the backward pointer of the VC to be removed to identify the immediately-preceding VC in the linked list so that the forward pointer of that immediately-preceding VC can be made equal to the forward pointer of the VC to be deleted, thereby reconstructing the linked list around the deleted VC. The need to provide backward pointers per VC makes the linked list processing complicated and also increases significantly the amount of information that the traffic manager must store.
In view of the problems identified above, it is desirable to provide an improved traffic manager and improved traffic managing method capable of handling disparate-rate VCs efficiently without requiring excessive processing power and/or storage capacity.
According to a first aspect of the present invention, there is provided scheduling circuitry, for scheduling predetermined events, including: a master calendar holding entries corresponding respectively to events that are to occur within a preselected master-calendar scheduling range; a slave calendar holding entries corresponding respectively to events that are to occur beyond said scheduling range; and calendar control circuitry operable, when an event is to be scheduled, to make an entry corresponding thereto in the slave calendar if the interval between a current time and a desired scheduling time for the event exceeds said scheduling range, the calendar control circuitry being further operable to monitor the entries in the slave calendar and to cause an entry therein whose corresponding event becomes within said scheduling range to be transferred to the master calendar.
According to a second aspect of the present invention there is provided a scheduling method, for scheduling predetermined events, wherein: when an event is to be scheduled, an entry corresponding thereto is made in a master calendar if the interval between a current time and a desired scheduling time for the event is within a preselected master-calendar scheduling range, and if said interval exceeds said preselected scheduling range an entry corresponding to the event is made in a slave calendar separate from the master calendar; and the entries in the slave calendar are monitored and any entry therein whose corresponding event becomes within said master-calendar scheduling range is transferred to the master calendar.